<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>图的封装</title>
</head>
<body>
    <script src="./tools/dict.js"></script>
    <script src="./tools/queue.js"></script>
    <script>
        function Graph (){
            // 属性
            this.vertexes = [] // 存储顶点
            this.adjList = new Dictionay() // 存储边
            /*
            * 方法
            * 我们规定形参 v 表示点 w 表示边
            */
            // 添加点
            Graph.prototype.addVertexes = function (v){
                this.vertexes.push(v)
                this.adjList.set(v,[]) // 给该顶点创建一个数组存储所有的边
            }

            // 添加边
            Graph.prototype.addEdge = function(v,w){
                this.adjList.get(v).push(w) // 根据v取出对应的数组并把w存进去
                this.adjList.get(w).push(v) // 根据w取出对应的数组并把v存进去
            }

            // toString方法用于显示结果
            Graph.prototype.toString = function (){
                var resultStr = ""
                for (let i = 0; i < this.vertexes.length; i++) {
                    // 获取到所有的点并用 --> 连接
                    resultStr += this.vertexes[i] + "-->"
                    // 获取到所有一个点包含所有的边
                    var abj = this.adjList.get(this.vertexes[i])
                    for (let j = 0; j < abj.length; j++) {
                        resultStr += abj[j] + " ";
                    }
                    resultStr += "\n"
                }
                return resultStr
            }
            
               /*图的遍历*/
            // 广度优先算法(基于队列,优先入队列的会被先探索)
            // 初始化颜色
            Graph.prototype.initializeColor = function (){
                /*
                * 我们用颜色表示当前的顶点是否被探索过  
                * 我们规定白色: 表示该顶点还没有被访问. 
                * 灰色: 表示该顶点被访问过, 但并未被探索过.
                * 黑色: 表示该顶点被访问过且被完全探索过.
                */
                var colors = [] 
                for (let i = 0; i < this.vertexes.length; i++) {
                    colors[this.vertexes[i]] = 'white'
                }
                return colors
            }
            // 广度优先搜索的实现
            Graph.prototype.bfs = function(v,handler){
                // 初始化颜色
                var color = this.initializeColor()
                // 创建队列
                var queue = new Queue()
                // 将顶点传入队列中
                queue.enqueue(v)
                while(!queue.isEmpty()){
                    // 从队列中取出数据 
                    var qv = queue.dequeue()
                    // 获取qv顶点所有的相邻顶点
                    var qAdj = this.adjList.get(qv)
                    // 将遍历过的颜色改为灰色表示已经被访问过了
                    color[qv] ="gray"
                    // 将qAdj所有的顶点压入队列中 (等于是访问了当前顶点以及同层顶点的所有顶点接下来要访问下一层顶点)
                    for (let i = 0; i < qAdj.length; i++) {
                        var a = qAdj[i];
                        // 如果访问的当前节点为白色 也就是没被访问过
                        if(color[a] ==='white'){
                            color[a] = 'gray'
                            // 将此顶顶存入队列中
                            queue.enqueue(a)
                        }
                    }
                    // 因为qv已经探索完毕,将qv设置为黑色
                    color[qv] = "black"
                    // 处理qv
                    if(handler){
                        handler(qv)
                    }
                }
            }

            // 深度优先搜索
            Graph.prototype.dfs = function (handler) {
                // 初始化颜色
                var color = this.initializeColor()
                for (let i = 0; i < this.vertexes.length; i++) {
                    // 如果访问的节点颜色为白色就代表未被访问过
                    if(color[this.vertexes[i]]==="white"){
                        this.dfsVisit(this.vertexes[i],color,handler)
                    }
                }
            }
            // 使用递归调用方法
            Graph.prototype.dfsVisit = function (u,color,handler){
                // 将当前节点设置为灰色
                color[u] = "gray"
                // 处理u顶点
                if(handler){
                    handler(u)
                }
                // u的所有邻接顶点的访问
                var uAdj = this.adjList.get(u)
                console.log('顶点为:'+u,'边为:'+uAdj);
                for (let i = 0; i < uAdj.length; i++) {
                    var w = uAdj[i];
                    console.log('边的颜色为:'+color[w]);
                    if(color[w]==="white"){
                        this.dfsVisit(w,color,handler)
                    }
                    
                }
                // 将u设置为黑色
                color[u] = "black"
            }
        }

        // 测试代码
        var graph = new Graph()
        // 添加顶点
        var myVertexes = ["A","B","C","D","E", "F", "G", "H", "I"]
        for (let i = 0; i < myVertexes.length; i++) {
            graph.addVertexes(myVertexes[i])
        }

        // 添加边
        graph.addEdge('A', 'B');
        graph.addEdge('A', 'C');
        graph.addEdge('A', 'D');
        graph.addEdge('C', 'D');
        graph.addEdge('C', 'G');
        graph.addEdge('D', 'G');
        graph.addEdge('D', 'H');
        graph.addEdge('B', 'E');
        graph.addEdge('B', 'F');
        graph.addEdge('E', 'I');
        alert(graph.toString());
        // 测试广度优先算法遍历
        var result = ""
        // 从A顶点开始遍历
        graph.bfs(graph.vertexes[0],function(v){
            result += v +""
        })
        alert(result); // A B C D E F G H I
        // 从E顶点开始遍历
        var resultE = ""
        graph.bfs(graph.vertexes[4],function(v){
            resultE += v +""
        })
        alert(resultE);// E F G H I
        // 深度优先探索
        var depthResult = ""
        graph.dfs(function(v){
            depthResult += v +""
        })
        alert("深度优先探索:"+depthResult);// E F G H I
    </script>
</body>
</html>